The following content has been provided by the University of Erlangen-Nürnberg.

Let's briefly recap what you, I think, have been doing for last week.

We're at the topic of constraint satisfaction problems and particularly how to solve them.

And you should have talked about the most naive and straightforward way to do that, namely we just consider it a search problem.

You've been doing search problems for a while, so you know basically what to do there.

The idea is basically we successively build up an assignment for all the variables in our constraint satisfaction problem

by just going via partial assignments, assigning one variable after the other.

And then we build up a search tree and basically have all of the full assignments at the leaves of our search tree.

Most of those will of course not work.

But the basic idea is that we do a depth-first search.

By the way, why would we do depth-first search instead of breadth-first?

Yes? Sorry?

Memory?

Memory? Yeah, sure, that's one reason.

But I just earlier said something that's highly relevant.

Well, all of the solutions are only at the leaves of the tree.

So doing breadth-first basically doesn't make much sense if we know exactly that all of our solutions will be somewhere here anyway.

Will always be at the lowest depth of the tree anyway.

So it makes sense to just run down there and check all of them.

And if we do that, the whole thing is called backtracking.

Basically just means we do depth-first, we check the first solution we find, namely the first leaf, check is that actually a valid solution.

If it's not, we just go to the next leaf, i.e. we go one step up, which is called backtracking, and then down the next one.

All of this is rather straightforward.

It's not exactly a smart algorithm, but you know it works.

Ultimately, a friend of mine once said that basically all of artificial intelligence can ultimately be reduced to A star.

Which is kind of true, but I mean, of course, all of this is horribly inefficient, so you should never try to actually solve any constraints or satisfaction problems by just doing tree search.

As it says here, you can solve the N Queen's problem for something like N approximately around 25.

Of course, this is just a basically random number, right?

I mean, if you can solve it for 25, you can solve it for 125, it's just that your machine will run forever.

So all of this is horribly inefficient.

But you know, it works.

And if you do that, the algorithm that you come up with is basically this, i.e. just go down, assign one variable after the other.

Once you have a full assignment, check whether that actually works.

If not, recurse, i.e. backtrack.

Here's just one example how you might do this.

We start with Australia.

The goal is to color every state, district.

No idea what they're called.

Territories.

Territories, OK.

You want to color every territory of Australia with one color such that no two neighboring districts have the same color.

And then you basically just randomly order your territories in some way.

In this case, we start with the one at the most left.

We have three colors, red, green, and blue.

So we have three choices to make.

Either we set our first variable to red, to green, or to blue.

And then from down there, we just branch, which gives us a nice tree.

And then we can do tree search.

Yeah, of course, this is the most naive approach, hence not exactly efficient.

But at least it's a starting point.